In a pipelined processor, taken branches in the instruction stream cause the throughput of the pipeline to fall well below optimal. When a taken branch is encountered, a break in execution occurs. As a result, a new instruction stream must be fetched in order for the execution to continue. The memory accesses For these target instructions must be made early enough to insure that the pipeline will not stall due to a lack of instructions ready for execution.
There are two basic types of branching typically implemented in a machine instruction set: 1) unconditional branches and 2) conditional branches. Unconditional branches will always result in a break in execution. Conditional branches will sometimes result in a break, and arc dependent upon the evaluation of some condition.
There is no penalty involved when executing a not-taken conditional branch (assuming that the processor continues to prefetch down the next sequential instruction path).
Only on unconditional branches and taken conditional branches does pipeline performance suffer. Several conditional branch prediction mechanisms are know in the art. These mechanisms attempt to make a prediction at the decode phase of the processor pipeline.
A Decode History Table (DHT) attempts to correctly prefetch the target instruction stream on conditional branches, by using past execution behavior as a predictor of future behavior. A table is constructed consisting or the past history of branch behavior (taken or not taken) and the table is addressed using a transformation of the branch instruction address. A DHT is described in U.S. Pat. No. 4,477,872 by Losq. The Decode History Table is interrogated at instruction decode time, so it is called a decode-time prediction scheme.
Several mechanisms are known in the art which attempt to predict the outcome of both conditional and unconditional branches. These mechanism make a prediction at the instruction fetch phase of the pipeline.
A Branch History Table (BHT) attempts to correctly prefetch tile target instruction stream, and does so for both conditional and unconditional branches. A BHT contains the past history of branch execution and also contains the target address for each taken branch. The BHT is interrogated at instruction fetch time, the earliest possible stage in tile instruction pipeline. A BHT is described in U.S. Pat. No. 3,559,183 by Sussenguth. The BHT is addressed with the current instruction fetch address.
DHT has the major advantage over the BHT of knowing that a branch actually is contained in the instruction stream. Thus a BHT entry must contain the entire instruction address (versus a transformation) and the entire target instruction address (versus allowing the DHT to compute tile address). The BHT though has the advantage of predicting the branch action much earlier in the pipeline, thus being able to reduce pipeline stalls much more effectively.
Both tables must have associated mechanisms to allow a back out if the prediction of the branch is wrong (this is called a Branch Wrong Guess (BWG)). There are many reasons why a prediction table may make an incorrect prediction. First the DHT BWGs will be discussed, followed by tile BHT BWGs.
A DHT BWG occurs when: 1) a collision occurs on tile transformation algorithm such that multiple addresses are mapping to the same entry, and their behavior is different, 2) a branch has a changing branch behavior (i.e. a taken branch changes to not taken, then back to taken, etc.), or 3) a branch ages out of the DHT due to a finite table size. Of these causes of a BWG, changing branch behavior is the most difficult to solve.
A BWG in a BHT is caused by: 1) a changing branch behavior, 2) a changing branch target address, or 3) a branch aging out of the BHT due to the finite table effect. Of these three problems, a changing behavior contributes to the majority of the BHT BWGs.
A major cause of BWGs is due to the frequent use in high-level languages of a multi-way branch that are based on the value of an operand or variable. Multi-way branches are known by various names, such as a switch or a select instruction. Typically a specific instruction introduces a multi-way branch and that specific instruction is often called a Case Statement. Whatever the name, such multi-way branches are generally implemented in a lower level language as a block of instructions which contains a plurality of branch instructions. Such a block of instructions herein is called a Case Block. The reason why a Case Block causes problems for DHTs and BHTs is that a Case Block execution is based on the value of an operand, which herein is referred to as the Case Variable. This operand (the Case Variable) typically changes on each entry into the Case Block. This causes branches in the Case Block that were taken on their last execution to be not taken on ensuing executions, and vice-versa, thereby generating BWGs.